#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size()==0){
            return true;
        }
        
        for(int i = 0;i<board.size();++i){
            for(int j = 0;j<board[0].size();++j){
                if(DFS(board,word,i,j,0)){
                    return true;
                }        
            }
        }
        return false;

    }
    bool DFS(vector<vector<char>>& board,string word,int i,int j,int k){
        if(i>=board.size()||i<0||j>=board[0].size()||j<0||board[i][j]!=word[k]){
            return false;
        }
        if(k==word.size()-1){
            return true;
        }
        board[i][j] = '\0';
        bool res = DFS(board,word,i+1,j,k+1)||DFS(board,word,i-1,j,k+1)||DFS(board,word,i,j-1,k+1)||DFS(board,word,i,j+1,k+1);
        board[i][j] = word[k];
        return res;
    }
};